/**
 * @Question.Title: 保证图可完全遍历
 * @Question.No: 1579
 * @Author: DQ
 * @Date: 2021-01-28 13:23:16
 * @Description: 
 */
//Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3 种类型的边： 
//
// 
// 类型 1：只能由 Alice 遍历。 
// 类型 2：只能由 Bob 遍历。 
// 类型 3：Alice 和 Bob 都可以遍历。 
// 
//
// 给你一个数组 edges ，其中 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请
//你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图
//是可以完全遍历的。 
//
// 返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
//输出：2
//解释：如果删除 [1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所
//以可以删除的最大边数是 2 。
// 
//
// 示例 2： 
//
// 
//
// 输入：n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
//输出：0
//解释：注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。
// 
//
// 示例 3： 
//
// 
//
// 输入：n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
//输出：-1
//解释：在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10^5 
// 1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2) 
// edges[i].length == 3 
// 1 <= edges[i][0] <= 3 
// 1 <= edges[i][1] < edges[i][2] <= n 
// 所有元组 (typei, ui, vi) 互不相同 
// 
// Related Topics 并查集 
// 👍 107 👎 0

package everyday.leetcode.editor.cn;

import com.dq.utils.CreateArray;

public class RemoveMaxNumberOfEdgesToKeepGraphFullyTraversable {
    public static void main(String[] args) {
        Solution solution = new RemoveMaxNumberOfEdgesToKeepGraphFullyTraversable().new Solution();
        int[][] edges = (int[][]) CreateArray.genIntArray("[[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]");
        int n = 4;
        System.out.println(solution.maxNumEdgesToRemove(n,edges));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private int[][] p;
        //联通分量数量
        private int[] pLen;
        public int maxNumEdgesToRemove(int n, int[][] edges) {

            p = new int[2][n];
            pLen = new int[]{n,n};
            int edgeUse = 0;
            //初始化
            for (int i = 0; i < n; i++) {
                p[0][i] = i;
                p[1][i] = i;
            }
            for (int i = 0; i < edges.length; i++) {
                if (edges[i][0] != 3) continue;
                int a = union(edges[i][1]-1, edges[i][2]-1,0);
                int b = union(edges[i][1]-1, edges[i][2]-1,1);
                if (a+b>0) edgeUse++;
            }
            for (int i = 0; i < edges.length; i++) {
                if (edges[i][0] == 3) continue;
                if(union(edges[i][1]-1, edges[i][2]-1,edges[i][0] - 1)==1){
                    edgeUse++;
                }
            }
            if(pLen[0]>0||pLen[1]>0) return -1;
            return edges.length - edgeUse;
        }
        private int findRoot(int x, int[] parent){
            while (x != parent[x]) {
                x = parent[x];
            }
            return x;
        }
        private int union(int x, int y, int i) {
            int[] parent = p[i];
            int xRoot = findRoot(x, parent);
            int yRoot = findRoot(y, parent);
            //返回0表示已经在一个连通量里
            if(xRoot == yRoot) return 0;
            parent[xRoot] = yRoot;
            pLen[i]--;
            return 1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}